﻿#define _CRT_SECURE_NO_WARNINGS 1

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//bool IsNo(vector<int>& v)
//{
//    sort(v.begin(), v.end());
//    for (int i = 2; i < v.size(); i++)
//    {
//        if (v[i - 1] == v[i] && v[i] != 0)
//        {
//            return true;;
//        }
//    }
//    return false;
//}
//int main()
//{
//    int n = 0;
//    int x = 0, count = 1;
//    vector<int> v;
//    cin >> n;
//    v.resize(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> v[i];
//        if (v[i] == i)
//        {
//            v[i] = 0;
//            x++;
//        }
//    }
//
//    if (IsNo(v))
//    {
//        cout << 0 << endl;
//    }
//    else
//    {
//        for (int i = 1; i <= x; i++)
//        {
//            count *= i;
//        }
//        cout << count << endl;
//    }
//    return 0;
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    int q = 0, x = 0;
//    cin >> q;
//    for (int i = 0; i < q; i++)
//    {
//        cin >> x;
//        if (x % 2 == 0)
//        {
//            cout << x << endl;
//        }
//        else
//        {
//            vector<int> v;
//            while (x)
//            {
//                v.push_back(x % 10);
//                x /= 10;
//            }
//            reverse(v.begin(), v.end());
//            int i = 0;
//            while (i < v.size())
//            {
//                if (v[i] % 2 == 0)
//                {
//                    swap(v[i], v.back());
//                    break;
//                }
//                i++;
//            }
//            if (i == v.size())
//            {
//                cout << -1 << endl;
//            }
//            else
//            {
//                for (i = 0; i < v.size() - 1; i++)
//                {
//                    cout << v[i];
//                }
//                cout << v.back() << endl;
//            }
//        }
//    }
//    return 0;
//}


//#include <iostream>
//using namespace std;
//int main()
//{
//    int n, m, k, i;
//    cin >> n >> m;
//    k = n;
//    for (i = 1; i < m; i++)
//    {
//        k *= (n - 1);
//        k %= 109;
//    }
//    cout << k << endl;
//	return 0;
//}


//贪心思想
//class Solution 
//{
//public:
//    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
//    {
//        vector<int> start;
//        vector<int> end;
//        //分别得到活动起始时间
//        for (int i = 0; i < n; i++)
//        {
//            start.push_back(startEnd[i][0]);
//            end.push_back(startEnd[i][1]);
//        }
//        //分别对开始和结束时间排序
//        sort(start.begin(), start.end());
//        sort(end.begin(), end.end());
//        int res = 0;
//        int j = 0;
//        for (int i = 0; i < n; i++)
//        {
//            //新开始的节目大于上一轮结束的时间，主持人不变
//            if (start[i] >= end[j])
//                j++;
//            else
//                //主持人增加
//                res++;
//        }
//        return res;
//    }
//};
